Skip to main content

Full text of "MICRO SPITBOL"

See other formats


Computer Science Department 



TECHNICAL REPORT 



MICRO SPITBOL 



Robert B. K. Dewar 
Martin Charles Golumbic 
Clinton F. Goss 



October I979 
Report No. Oil 











K) 



NEW YORK UNIVERSITY 




Department of Computer Science 
Courant Institute of Mathematical Sciences 

251 MERCER STREET, NEW YORK, N.Y. 10012 



MICRO SPITBOL 



By 

Robert B. K. Dewar 
Martin Charles Golumbic 
Clinton F. Goss 



October I979 
Report No. Oil 



This material is based upon work supported in part by the National Science 
Foundation under Grant No. MCS78-O382O. 

Any opinions, findings, and conclusions or recommondations expressed in this 
publication are those of the authors and do not necessarily reflect the 
views of the National Science Foundation. 



Abstract 

A compact version of MACRO SPITBOL, a compiler/ interpreter for a 
variant of SNOBOLU, has been developed for use on microcomputer systems. 
The techniques for producing an implementation are largely automatic in 
order to preserve the integrity and portability of the SPITBOL system. 
These techniques are discussed along with a description of an initial 
implementation on a 65K byte minicomputer. An interesting theoretical 
problem which arises when using procedures which compact the interpretive 
object code is also analyzed. 

Keywords: SNOBOLii, Compiler, Interpretive code, Microprocessors, 
Portability, Weighted Interval Graph 



MACRO SPITBOL (1"! is a compiler/ interpreter for a variant of SNOBOLU (3), 
SPITBOL (k) , which has been implemented on a variety of large computers. 
MICRO SPITBOL is an adaptation of the system for use on micro and 
minicomputers which compiles a language identical to MACRO SPITBOL with the 
exclusion of real arithmetic. The goal was to preserve the structure and 
machine independence of the system while allowing for the added constraints 
imposed by small computers, particularly the severe limitations on memory and 
address size. We also intended that the process for implementing MICRO 
SPITBOL on a minicomputer be largely automated. In this way we preserve 
the integrity of the well-tested MACRO SPITBOL source code while allowing 
for easy updating to new versions. 

These goals were attained by encoding the MACRO SPITBOL source code, 
written in the MINIMAL assembly language (5), into a compact 
microcomputer assembly language, MICRAL. In a MACRO SPITBOL implementation 
the MINIMAL source code is translated into the target machine's assembly 
language and directly executed; The target MICRO SPITBOL machine emulates 
a standard virtual microcomputer (MICRAC) which executes MICRAL code. This 
interpretive approach preserves the portability of MINIMAL programs while 
dealing with the problems and constraints imposed on MICRO SPITBOL. 

MICRO SPITBOL is implemented on the Incoterm SPD 20/U0 (6), a 65K 
byte minicomputer, and versions are in preparation for microcomputers based 
on the IMS 808O and M68OO processors. Th Incoterm implementation has been 
exercised with an extensive test package and appears very sound. It 
provides about 2/5 of memory for the user heap in which UOO to 500 
SPITBOL statements may be compiled. The current version executes an average 
of 20 SPITBOL statements per second; This is l/lUO the execution speed of 
the CDC 6600 version. 



MICRAL - Micro Computer Assembly Language 
MICRAL (2) is an encoding of MINIMAL suitable for direct translation to 
an interpretive form to run on a mini or microcomputer system with a I6 bit 
addressing structure and 8 bit bytes. The layout of a MICRAL program and the 
environment in which it runs are similar to that of a MINIMAL program. However, 
MICRAL source code is largely non-symbolic; Most of the work in converting 
MICRAL to its interpretive form involves address resolution, a feature 
available on even the most primative assemblers. 

Unlike MINIMAL, MICRAL assumes no minimum hardware configuration since 
its machine code is interpretive. In fact, the object code for a given MICRAL 
program does not vary among machines with the exception of absolute addresses. 
Thus the sophistication of the target machine's instruction set determines 
only the speed at which the MICRAL object code is interpreted and not the 
size of the code, as in MINIMAL. 

The general format of MICRAL source code is typical of many assembly 
languages. The opcode is one of 80 mnemonic instructions which is translated 
into a single byte (x'OO' to x'UF'). The operand field is a (possibly empty) 
series of items separated by commas. Each item is one of the following: 

1) A two or four digit hexidecimal number which is assembled into one 
or two object bytes j 

2) A five character label appearing in the MICRAL program or a system 
subroutine. This is eventually translated into the two byte absolute 
address of the label; 

3) A five character label preceded by a '+' or '-'. This form of an 
address reference is used to generate a special single byte address 
which will be discussed later. 

To represent MINIMAL operands in MICRAL, the byte following the opcode 
is used to specify the format of the first two operands. This byte, the 
operand header byte, contains information about the first operand in its 



four low order bits and information about the second operand in its four 
high order bits. In frequent cases (references to the contents of the six 
virtual registers) , the MINIMAL operand is completely specified in the header 
byte. 

For example, the MINIMAL instruction < MOV WA,-(XS) > is encoded in 
MICRAL as < MOV 90 > since x'O' is the four bit code for the contents of 
the WA register and x'9' indicates the contents of the word indexed by (XS) 
with a pre-decrement on XS. If additional fields are required to fully 
specify a MINIMAL operand, they directly follow the operand header byte. 
The fields for the first two operands may be followed by a field for the 
possible third operand. For example, the MINIMAL < BEQ WA,=X'00FF' , LABEL > 
would be encoded as < BEQ BO, OOFF, LABEL > since x'B' indicates a literal 
value for the second MINIMAL operand. 

In accordance with the space efficient philosophy of MICRAL there are 
several modifications we apply to the language as we have described it. 

First we restrict all literal values and offsets to be in the range 
to x'7FFF' . This allows literals in the range to x'7F' to be expressed as 
a single byte whose value is x'80'+literal. 

In a similar style, we convert local memory references to a single byte 
by requiring that all labels in the MICRAL program and system routines take 
on a value less than x'8000'. We express a jump address, ADR, which is in 
the range (L - x'l+O') to (L + x'3F') (where L is the current location) as a 
single byte containing (L + x'CO' - ADR). These short branch instructions are 
recognized during the translation from MINIMAL to MICRAL and are indicated 
by substituting '-LABEL' or '+LABEL' for 'LABEL' whenever LABEL is in 
range. 



The final and most space efficient optimization employed is the use of 
macros. MICRAL macros utilize the I76 unused opcodes x'50' to x'FF' for 
representing sequences of bytes in the MICRAL object code. These sequences of 
bytes may be a single MICRAL instruction, part of an instruction, or several 
instructions. Note that macros never include bytes corresponding to the one 
byte offset form of jump addresses, so the question of where to count the 
offset from does not arise. Also, a macro opcode may never be substituted for 
a sequence of bytes which have an embedded label in the source code. This 
eliminates jumping into the 'middle' of a macro. Also, it is not possible to 
embed a macro in another macro, thus eliminating the necessity for 
environment stacking when interpreting the macros. 

Macros may be interpreted by the MICRAC emulator in one of two ways. 
A table of the MICRAL bytes corresponding to each macro may be referenced when 
a macro is encountered. The emulator interprets the bytes obtained from the 
macro table as if they had appeared in the MICRAL program. The number of 
bytes for each macro is also maintained within the macro table and, when the 
macro bytes are exausted, interpretation returns to the main byte string. 

Alternately, some or all of the macros may be directly hand encoded into 
the target machine language. This latter approach requires more space, but 
increases execution speed. 



The PD/FMS Implementation 

The Incoterm SPD 20/i+0 is a byte oriented single address minicomputer 
with indexing and multi-level indirect addressing. It supports up to 65K 
bytes of magnetic core memory with a cycle time of 1.6 microseconds. MICRO 
SPITBOL is implemented under the Program Development/File Management System 
(PD/FMS) (7) which provides for task control and device handling via a package 
of relocatable routines. 

Minimum hardware for running MICRO SPITBOL consists of the central 
processor with 65K bytes of memory, a CRT/keyboard unit, and a 10 megabyte 
cartridge disk drive. Additional supported hardware includes 7 CRT/keyboard 
units, a printer, and 3 cartridge disk drives. 

The details of the PD/EMS implementation were as follows: 

The MACRO SPITBOL source code, written in MINIMAL, was translated to 
MICRAL source code by MICTRAN, a program coded in SPITBOL. It is a variation 
of a SPITBOL translator used for generating native assembly code from 
MINIMAL. It recognizes the short form of literals and branch instructions 
as described earlier. The program was run on a CDC 6600 and processed the 
10,000 MINIMAL instructions in 20 cpu seconds. Figure 1 is an example of the 
code produced by MICTRAN. The MICRAL source code along with the error text 
file were then exported to the Incoterm system where the remainder of the 
implementation was done. 

The next stage was to determine the sequences of macros to employ in 
translating the MICRAL source code to SPD assembly code (8). We first examined 
the problem theoretically to determine whether there is an algorithm for giving 
optimal or near optimal results. The problem is interesting since, although the 
computation may be performed in polyiiomial time, the complexity of the optimal 
algorithm is a polynomial whose degree depends on the number of macros chosen: 



finding the u macros which minimize the length of t\ bytes of object code is 
OCC'H't) /(d-2).') where -t is the maximum length of a macro. Another approach 
which produces near optimal results and does allow embedding of macros requires 



0(i:)(T)+-^'£logpT]) ) time. The analysis of this problem is presented in the 
appendix. 

In practice, this theoretical complexity is troublesome since version 
3.3B of MICRO SPITBOL requires 23,110 bytes of MICRAL object code before 
macro substitution. Also, implementation of the algorithms analyzed in the 
appendix is difficult due to the numerous constraints on the allowable 
macros. Since macros may not contain short branches or embedded labels, 
choosing macros must be done from the source code and not the resulting byte 
string. Also, since additional short branches become available as macros are 
introduced, the computation of the length of the object code after a macro 

substitution is dependent on many factors. 

Due to the desire for a speedy implementation, it was decided to restrict 
macros to a single instruction or part of an instruction and no use of hand 
encodings or short branches was made. The MICRAL source code was sorted 
lexicographically with the opcode field as the first key and the operand 
field as the second key. The sorted list was then scanned by hand to count the 
number of each operational MICRAL instruction or part instruction. The number 
of bytes saved by converting each sequence to a macro was then computed for 
each such instruction and multiplied by the number of occurrences. The I76 
byte sequences which produced the highest savings were chosen as macros. 

The MICRAL source code and the chosen macros were then processed by 
MICASM, which translates MICRAL to SPD assembly source code (see Figures 2 
and 3). This program is coded in SPD assembly language and processes 65 lines 
per second. The resulting assembly language file was then assembled into a 
relocatable module. The size of that module with macro substitutions is 
17,920 bytes, an improvement of 5,190 bytes over the corresponding module 
without macro substitutions. 



7 
To interpret the MICRAL object code, another module was included in 
the absolute assembly. This module, known as the MICRAC emulator, consists of 
3,020 lines of code and takes 2,230 bytes of memory. Since its size is small 
compared to the MICRAL object code, the emulator is one area of the system in 
which speed considerations took priority over space. 

Finally, a set of modules consisting of PD/FMS routines for task control, 
timer control, and screen, disk, and printer handling were included in the 
absolute assembly. These routines are accessed by SPITBOL through a set of 
system routines which are called directly by the MICRAL code. The system 
routines were coded in SPD assembly language and are part of the mainline 
MICRO SPITBOL file (the absolute assembly). In addition to the system routines, 
this file contains the macro sequences and allocates space for the relocatable 
modules and the SPITBOL heap. It is 51^0 lines of code and occupies the full 
65K bytes, 28k bytes of which are the user heap. 

The PD/FMS implementation has been exercised on a variety of test 
programs and appears very stable. Performance evaluation was done with a 
package of 2k programs which have an average length of 70 statements. The 
test set was run under version 3.3B of MACRO SPITBOL on the CDC 66OO for 
comparison. MICRO SPITBOL compiled at an average rate of I.3 statements per 
second and executed at 19.7 statements per second. The corresponding values for 
MACRO SPITBOL were I86.9 statements per second for compilation and 2,829 
statements per second for execution. 



Conclusion 

The implementation of MICRO SPITBOL was broken down into two major 
stages. 

First, the design and implementation of programs for converting from 
MINIMAL to the interpretive MICRAL code, choosing appropriate macros, and 
converting from MICRAL to assembly language, required about three man-months 
work. 

The second stage entailed work specific to the PD/FMS implementation. 
This included coding the MICRAC emulator and system routines in SPD assembly 
language which, for the PD/FMS implementation, took about 1 man-month work. 
For subsequent implementations it is only this latter stage which is needed 
since the MICRAL object code and macros are fixed for a given version of 
MICRO SPITBOL and only minor changes in MICASM are necessary to accomodate 
various native assembly language formats. 

Also, since the process of translation for MICRAL is now automated, any 
program coded in MINIMAL may now be implemented by this scheme. 

The PD/FMS version currently allows lj-00 to 500 'typical' SPITBOL 
statements to be compiled. Again, since the MICRAL object code does not vary 
among implementations, this figure should remain fairly constant for 
microcomputers with 65K bytes of memory. 

The cost of the extra level of interpretation necessary to emulate the 
MICRAC machine is evident in the two order drop in execution speed from MACRO 
SPITBOL on the CDC 660O to the PD/FMS implementation. However, the Incoterm 
instruction set is rudimentary compared to other target microcomputers, so 
an improvement in execution speed may be expected on other processors. Extra 
speed may also be gained by utilizing some of the unused design features of 
MICRAL such as hand encodings for macros. Also, a better selection of 



9 
substitution macros will have a positive effect on both processing speed and 
space. Better macros may be selected by implementing one of the algorithms 
suggested in the appendix, with the possible addition of some efficient 
heuristics. 

Due to the decreasing cost of memory, the space constraints experienced 
in this implementation will probably disappear. Memory may become so inexpensive 
that a direct translation of the MINIMAL code to the target machine code 
would be preferable for small MINIMAL programs. However, for large MINIMAL 
programs, or on processors with a low level instruction set, the techniques 
used in the implementation of MICRO SPITBOL may be more suitable. Since these 
systems are typically single-user, the availability of very high level 
languages outweighs the loss of processing speed for many applications. 



10 

Appendix 

We now analyze the problem of finding a set of macro substitutions which 
minimizes the space required for the object code and macro table. We ignore 
the complications which arise when the short form of branches are used in the 
object code byte string since we have not implemented this aspect of 
MICRAL. 

Let B = <b]^,...,b^> be a sequence of bytes. The length of B is denoted 
|b| = ri. A subsequence of B, <b^,..,,b.>, is denoted B(i:j). 

A macro set is a set M = {m-|^, . . . ^m^) where each macro m^ is a sequence 
of bytes. The size of the macro table corresponding to M is given by 

■0 

Mm|| = I ItBil . 

i=l 

Since macros may not include a labelled byte other than the first byte, macros 
tend to be short compared to IbI. To aid in the analysis, we restrict the 
length of macros, Im. I < -t . 

A macro substitution is an operation on a byte sequence in which all 
occurrences of a given subsequence of bytes are replaced by a single byte. 
In case of overlapping occurrences of the subsequence, the leftmost occurrence 
is replaced. The byte sequence resulting from the substitution of all macros in 
a macro set, M, on a byte sequence, B, is denoted B(M) . The goal is to find, 
for a given byte sequence, B, a macro set, M, which minimizes the length 
function 

l(b,m) = |b(m)| + ||m|| 



11 

We shall analyze the worst case involved in a complete search strategy. 
For .1=1, the problem reduces to finding the best single macro for a byte 
sequence. Algorithm A performs this function using a table, FREQ, which maps 
subsequences of B onto a count of their occurrences in B. 

Algorithm A: 

1) For k from 1 to ■t-'i-, perform steps 2 and 3- 

2) For each subsequence of B, B(i:i+k.), increment FREQ(B( i : i+k) ) . 

3) Set m(k) to a subsequence such that FREQ(m(k)) is maximal. Then set: 

L(B,{m(k)}) = |b| - (|m(k) !-l)*(FREQ(m(k))-l) + 1 

h) The best macro is the m(i) which minimizes L(B,{m(k)}) in step 3, 
5) Substitute the macro m(i) in B. 

Steps 2 and 3 are iterated over 0(-{,) times. Step 2 requires 0{t\) time 
to scan the subsequences and the map FREQ, if implemented as a balanced binary 
search tree, requires ©(loggT]) to maintain. Step 3 is linear if, during step 
2, a pointer to the macro with the greatest FREQ is kept. Step h may also be 
done in this fashion in linear time. Performing step 5 may be done by a 
modification of the deterministic finite automaton pattern matching algorithm 
presented in Morris and Pratt (9) and expanded in Aho, Hopcroft, and Ullman (10) 
This algorithm requires 0(|b| + |m(i)|) = 0{T\+'t) time. Note that we perform 
step 5 by finding the leftmost occurrence of m(i), substitute for it, and 
continue to the right. 

Therefore, Algorithm A runs in OCi^+'tl-Ti'D-oggTi) time. 

For u > 1, one would expect that an iterative application of Algorithm A 
would be effective. However, an optimal choice for the first macro does not 



12 

necessarily lead to an optimal macro set. For example, if 

B=<j,a,b,c,d,e,f,m,r,h,a,b,c,d,e,g,k,c,d,e,f,n,s,h,a,b,c,p> 
a choice of m^ = <a,b,c,d,e> yields L(B,[m^}) = 25 which is optimal for io=l. 
However, any choice for ra will force L(B,(m^,m }) > 25. If ^-^ = <c,d,e,£> 
and m = <h,a,b,c>, then L(B,[m^}) = 26 and UB ,[m^,m^]) = 2U. 

Furthermore, our algorithm for pattern matching may not produce optimal 
results in cases where a macro overlaps itself. Substituting for the second 
occurrence in an overlapping pair may lead to a better choice for other 
macros. This forces the recognition of each occurence of a macro and treatment 
of overlapping occurences as separate cases. 

We now characterize the problem of finding an optimal macro set by a 
graph theoretic representation. 

A weighted graph G = (V,E,W) consists of a binary relation E over a finite 
set V of vertices, and an integer valued mapping W defined over V, G is an 
interval graph if its vertices can be put into 1-1 correspondence with a set of 
intervals on a line so that two vertices are adjacent if and only if their 
corresponding intervals intersect. If B is a sequence of bytes, G(B), the 
weighted interval graph corresponding to B, is defined as follows: Each vertex 
in V represents a substring of B which may be used as a macro j Vertices v. and 
v. are connected by an edge in E iff the occurrences of the substrings represented 
by V. and v. overlap in B. If V is a vertex representing an occurrence of the 
substring m, then W(v) = !m| - 1 . 

If S is a subset of vertices from V, the subgraph of G induced by S, 
denoted G , consists of all vertices of S together with all edges from E which 
connect those vertices. 

To construct G(B), the ©(rj-t) possible macros in B are scanned and one 
vertex is added to V for each. Whenever a vertex is added to V, edges are 



13 

added to E for each overlapping macro pair. Since adding edges takes O(-c^) 
time with efficient data structures for the graph, G(B) is constructed in 
OCri-t ) time. 

To find the macro set, M, which minimizes L(B,M), we apply the following 
algorithm: 

Algorithm B: 

1) Calculate G(B). 

2) Partition the vertices of G(B) such that each partition contains 
vertices which represent occurrences of identical substrings in B. 

3) Let C be the set of all possible combinations of u partitions. For 
each set of combinations in C perform step h. 

k) Let S be the vertices in the D partitions. Let M be the macro set 
consisting of the u distinct byte sequences corresponding to the 
vertices of S. Occurrences of the macros in M are chosen in B 
such that no occurrences overlap. The problem of choosing the best 
set of occurrences is analogous to finding the maximum weighted 
independent set of vertices, I , in G . Then 



L(B,Mg) = |B| - I W(v) + I W(s) . 

vel seS 

5) The macro set, M, which minimizes L(B,M) is then determined by 

choosing an M which minimizes L(B,M ) in step h. 
o o 

Gilmore and Hoffman (11) characterized interval graphs by showing them 

to be a subclass of chordal graphs. This class of graphs has the property 

that, for every simple cycle [v, ,v , ,,.,v ,v ] (n>3), there is an edge 

(v.,v.) in E such that v. and v. are in the cycle but the edge is not. 

1 J 1 J ■' ^ 



11; 



2 
Gavril (12) gives an 0(|v| ) algorithm for finding the maximum weighted 

independent set of a chordal graph. The algorithm is also presented in 

Golumbic(13) with suitable data structures. See also Booth and Leuker (lU). 

, 2 
Thus, step 3 nisy be performed in 0((utv) ) time (note that the number of 

vertices in any induced subgraph is bounded by i:)ri). Step 3 must be performed 

at most (^ ; times. Hence, the worst case time complexity of algorithm B is 



o((Tl^^ + {^y^f (^3) , 



which is, in terms of the length of the input string, a polynomial whose 
degree depends on the constant u. In the example of this paper, r] is 23,000, 
u is 176, and a reasonable -t would be 20. With values in this range, the 
above complexity approximates and is bounded by 

o((^^)'^^ / (13-2):) . 

Since the time complexity of Algorithm B is high for this application, 
an effective algorithm for finding a near optimal solution is needed. One 
such heuristic approach would', be an iterative application of Algorithm A 
whose time complexity is 

0(u(Ti+^^Log2Ti)) . 

Such an approach may potentially produce better results than Algorithm 
B since it allows the embedding of macros within other macros, a feature 
prohibited in Algorithm B. Although, one could theoretically include this 
embedding feature in a method similar to Algorithm B by using the weighted 
overlap graph model as described in Gavril (15) and Golumbic( I3) • 



15 



EXIXR EXIXR RTN 

MOV 9k MOV XR,-(XS) STACK RESULT 

EXITS EXITS RTH 

LCW 014 LCH XR LOAD CODE WORD 

MOV 37 MOV (XR),XL LOAD ENTRY ADR 

BRI 03 BRI XL EXECUTE NEXT CODE 

EXNAM EXNAF RTN 

MOV 93 MOV XL,-(XS) STACK NAh'E BASE 

MOV 90 MOV WA,-(XS) STACK NAME OFSET 

BRN EXITS BRN EXITS DO NEXT CODE WORD 

EXNUL EXNUL RTN 

MOV 9B, NULLS MOV =NULLS,-(XS) STACK NULL VALUE 

BRN EXITS BRN EXITS DO NEXT CODE WORD 

FXSID EXSID RTN 

MOV OA 25 MOV CURID,WA LOAD CURRENT ID 

BNE B0!7FFF,+EXSI1 BNE WA, =CFP$M, EXS I 1 JUMP NO OVFL 

ZER 00 ZER WA RESET FOR V/RAP 

EXSIl ICV 00 EXSIl ICV WA BUMP ID VALUE 

MOV AO 25 MOV WA^CURID STORE FOR NEXT 

MOV EO'82 MOV WAJDVAL(XR) STORE ID VALUE 

BRN ExixR BRN EXIXR EXIT WITH RESULT 



Figure 1. Example of MINIMAL code (right) translated to 
MICRAL (left) by MICTRAN. 



16 



EXIXR EQU $ EXIXR 

HEX 329U 

EXITS EQU $ EXITS 

HEX 2A0tt 

HEX 3237 

HEX 0B03 

EXNAM EQU $ EXNAM 



EXNUL EQU $ EXNUL 



EQU 


$ 


HEX 


329U 


EQU 


$ 


HEX 


2A0tt 


HEX 


3237 


HEX 


0B03 


EQU 


$ 


HEX 


3293 


HEX 


3290 


HEX 


030C 


ADDR 


EXITS 


EQU 


$ 


HEX 


329B 


ADDR 


NULLS 


HEX 


n30C 


ADDR 


EXITS 


EQU 


$ 


HEX 


320A25 


HEX 


09B07FFF 


ADDR 


EXSIl 


HEX 


UUOO 


HEX 


ICOO 


HEX 


32A025 


HEX 


32E082 


HEX 


03 


ADDR 


EXIXR 



EXSID EQU $ EXSID 



EXSIl HEX ICOO EXSIl 



MOV 91+ STACK RESl'LT 

LCW Ok LOAD NEXT CODE WORD 

MOV 37 LOAD ENTRY ADDRESS 

BRI 03 EXECUTE NEXT CODE 

MOV 93 STACK NAME BASE 

MOV 90 STACK NAME OFSET 

BRN EXITS DO NEXT CODE WORD 



MOV 9B, NULLS STACK NULL VALUE 
BRN EXITS DO NEXT CODE WORD 



MOV 


0A,25 


LOAD CURRENT ID 


BNE 


B0,7FFF 


,+EXSIl 


ZER 


00 


RESET FOP WRAP 


ICV 


00 


BUMP ID VALUE 


MOV 


A0,25 


STORE FOP NEXT T 


MOV 


EG, 82 


STORE ID VALUE 


BRN 


EXIXR 


EXIT WITH RESULT 



ME 



Figure 2. Example of translation from MICRAL to SPD 
assembly code with no macro substitution. 



17 



EXIXR EQU $ EXIXR 

HEX 6A *** MOV 9k STACK RESULT 

EXITS EQU $ EXITS 

HEX 2A0I+ LCW OU LOAD NEXT CODE WORD 

HEX 89 *** MOV 37 LOAD ENTRY ADDRESS 

HEX 0B03 BRI 03 EXECUTE NEXT CODE 

EXNAM EQU $ EXNAM 

HEX 68 *** MOV 93 STACK NAME BASE 

HEX 60 *** MOV 90 STACK OFSET 

HEX El *** BRN EXITS DO NEXT CODE WORD 

EXNUL EQU $ EXNUL 

HEX 68 *** MOV 9B, NULLS STACK NULL VALUE 

ADDR NULLS 

HEX El *** BRN EXITS DO NEXT CODE WORD 

EXSID EQU $ EXSID 

HEX 9A *** MOV 0A,25 LOAD CURRENT ID 

HEX 25 

HEX EC *** BNE BO, 7FFF^ +EXSI 1 

HEX 7FFF 

ADDR EXSIl 

HEX ttUOO ZER 00 RESET FOR WRAP 

EXSIl HEX ICOO EXSIl I CV 00 BI'MP ID VALUE 

HEX 67 *** MOV A0,25 STORE FOP NEXT TIME 

HEX 25 

HEX 5D *** MOV E0,82 STORE ID VALUE 

HEX EO *** BRN EXIXR EXIT WITH RESULT 



Figure 3. Example of translation from MICRAL to SPD 
assembly code with macro substitutions. 
<***> indicates the use of a macro. 



18 
Bibliography 

1) Dewar, R.B.K. and McCann, A. P., 'MACRO SPITBOL - a SNOBOLU Compiler', 

Software - Practice and Experience, 7 (I977), pp. 95-113. 

2) Dewar, R. B. K. and Goss, C. F. , MICRAL - Language Description and Documentation , 

available from the authors. 

3) Priswold, R.E,, Poage, J.F. , and Polonsky, I. P., The SNOBOLli Programming 

Language , Second Edition, Prentice-Hall, Englewood Cliffs, N.J., 

256 pp., 1971. 
h) Dewar, R.B.K. , 'SPITBOL Version 2,0', IIT Internal Report, 78 pp., I97I. 

5) Dewar, R.B.K., McCann, A. P., 'MINIMAL - A Machine Independent Assembly 

Language', Computer Science Department Technical Report, Courant Institute 
of Mathematical Sciences, No. 012. 

6) SPD 20/20 Multi - station Intellegent Terminal System - System Description , 

Incoterm Corp., Wellesley Hilla, Mass., 02181, MS-7I65.I, January, I976. 

7) PD/FMS Programmers ' Reference Manual , Incoterm Corp., Wellesley Hills, 

Mass. , 02181, MS-7233.6. 

8) Incoterm SPD Assembly Language , Incoterm Corp., Wellesley Hills, Mass., 

02181, MS-7215.2. 

9) Morris, J.H. and Pratt, V. R, , 'A linear pattern matching algorithm'. Tech. 

Report No. i+O, Computing Center, University of California, Berkley (I97O). 

10) Aho, A. v., Hopcroft, J.E., and Ullman, J.D. , The Design and Analysis of 

Computer Algorithms . Addison -Wesley , I976. 

11) Gilmore, P.C. and Hoffman, A.J., 'A characterization of comparability 

graphs and of interval graphs', Canadian Journal of Mathematics, 
16 (196U), pp. 539-5it3. 



19 



12) Gavril, F. , 'Algorithms for minimum coloring, maximum clique, minimum 

covering by cliques, and maximum independent set of a chordal graph' 
SIAM Journal of Computing, 1 (I972), No. 2, pp. I8O-I87. 

13) Golumbic, M.C. , Algorithmic Graph Theory and Perfect Graphs , Academic 

Press. New York, N.Y., I96O . 
Ill) Booth, K.S. and Leuker, G. S., 'Testing for the consecutive ones property, 

interval graphs, and graph planarity using PQ-tree algorithms', 

J. Computer Sys. Sci. , 13(1976), 335-379. 
15) Gavril, F. , 'Algorithms for a maximum clique and a minimum independent 

set of a circle graph', Networks, 3(1973), 261-273. 



This book may be kept 

FOURTEEN DAYS 

A fine will be charged for each day the book is kept overtime. 
















1 


























































































































CAYLORD 142 









NYU 
Comp.Sci.Dept . 
TR-011 

Dewar 

MICRO SPITBOL. 



C.2 



NYU " 
Com^pjSgj^Dept. 

Dewar 



C.2 



AUTHOR 

MICRO SPITBOL. 



TITLE 



DATE DUE 



BORROWER'S NAME 



N.Y.U. Courant Institute of 
Mathematical Sciences 

251 Mercer St. 
New York, N. Y. 10012